class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int sz = nums.size(), ret = 1;
        vector<int> memo(sz);
        for(int i = 0; i < sz; ++i)
        {
            ret = max(ret, dfs(i, nums, memo));
        }
        return ret;
    }
 
    int dfs(int pos, vector<int>& nums, vector<int>& memo)
    {
        if(memo[pos] != 0)
            return memo[pos];
        int sz = nums.size(), ret = 1;
        for(int i = pos + 1; i < sz; ++i)
        {
            if(nums[i] > nums[pos])
                ret = max(ret, dfs(i, nums, memo) + 1);
        }
        memo[pos] = ret;
        return ret;
    }
};